1. Field of the Invention
The present invention generally relates to multi-processor computer systems, and more specifically, to scheduling the execution of tasks in such computer systems.
2. Background Art
Schedulers are used at many levels in computing systems, ranging from the low levels of operating systems up to the middleware and application level. Their function is to define an ordering for the execution of tasks according to a defined metric. A weighted fair-share scheduler is a scheduler that respects the importance and urgency of tasks by assigning a weight to each task. If a task is of high weight, it will rather and more often be scheduled than a task of lower weight. Different strategies exist to decide which task to schedule next: introducing deadlines (in virtual time as well as in real time), assigning credits to tasks, or using randomization strategies. The basic data structure for a weighted fair-share scheduler is the priority queue.
The recent trend in hardware to build multiprocessors, rather than faster CPUs, strongly encourages the distribution of software systems to enable full exploitation of parallelism. A distributed scheduler takes advantage of the parallelism offered by multi-core CPUs. Since the priority queue is hard to parallelize, most solutions making use of many threads accessing this data structure lead to an unacceptable amount of contention. This fact reduces the performance and scalability of most concurrent priority queues (and thus of distributed schedulers).
In a soft real-time system like a time-sensitive publisher/subscriber engine, variances that come along in high contention scenarios are even more critical. Publish/subscribe is a method by which data is organized in topics. All messages published on a topic are received by all subscribers to that topic. As one example, a time-sensitive, work-conserving publisher/subscriber engine may be used to guarantee each topic a share of the available resources. The core component of the engine is the weighted-fair share scheduler that schedules topics according to their guaranteed share.
As long as there is only one processor, using a priority queue, combined with e.g. an Earliest Deadline First (EDF) schedule, solves this problem trivially. On multi-core architectures, there is more than one processor which is able to serve a topic. This can be exploited by using concurrent priority queues, which allow many threads to access the data structure. The complexity of this approach is a major drawback.